1. Field of the Invention
The present invention relates to a method and a device for controlling routes, and to a computer program used for controlling the routes. More specifically, the present invention relates to a method, a device, and computer program for controlling routes used in a network which is temporary formed among a plurality of nodes, such as a so-called multi-hop network.
2. Description of Related Art
Research and development in so-called multi-hop (or ad hoc) networks have began. A multi-hop network is a network formed by a plurality of nodes, each of which functioning as a router. For example, a home network which is temporarily formed among a plurality of terminals capable of short range communication and in which information consumer electronics are mutually connected by wireless communication called Bluetooth, and a temporary network formed in a conference are presumed to be multi-hop networks.
Here, examples of system used in such networks will be briefly explained. As shown in FIG. 9, routes from the node S from which data are transmitted (hereinafter also referred to as a transmission source node) to the node D to which the data are sent (hereinafter also referred to as a destination node) are supplied through nodes N1-N4 which relay data packets. In the case shown in FIG. 9, if the node N1 moves outside of the network, the link between the node N1 and the node S is broken. However, since the route connecting S, N3, N4, and D is still available, it is possible to connect the node S to the node D by selecting this route while restoring the disconnected route.
On the other hand, if the link between the nodes S and N1 is overlapped as shown in FIG. 10 (in comparison with FIG. 9), all of the routes will be disconnected and cannot be restored if the link between the nodes S and N1 is broken. For this reason, it is necessary to control routes so that the routes will be formed with as few overlapping links as possible as shown in FIG. 9.
As methods for controlling routes in an ad hoc network, Dynamic Source Routing (DSR) method and Ad hoc On-demand Distance Vector Protocol (AODV), for example, are available. Also, a method obtained by expanding the AODV, which is called Ad hoc On-demand Multipath Distance Vector Protocol (AOMDV) has been proposed (refer to M. K. Marina and S. R. Das, “In Proceedings of the International Conference for Network Protocol”, November 2001).
The AOMDV is a protocol for forming a plurality of routes which do not contain overlapped links such as the one shown in FIG. 10. Here, the procedure for forming routes using the AOMDV will be explained with reference to FIG. 11. First, the node S broadcasts a message (RREQ) for searching the node D. The message contains an area in which the address of the node which first receives the message will be registered, and nothing is registered at this area when the message is transmitted from the node S. The nodes N1 and N2 which received the message recognize that they are the nodes which first received the message, and registers the address thereof in the above-mentioned area. Then, the nodes N1 and N2 broadcast the message. The node I which received the message from both the nodes N1 and N2, only acquires the message which is received earlier, i.e., the message from N1 in the figure, and abandons the other message, i.e., the message from N2. Then, the node I broadcasts the message, and the message is transmitted to the node D via the nodes N3 and N4 to establish the transfer routes. The node D unicasts a reply message (RREP) to the nodes N3 and N4 which broadcasted the message, and thereafter each of the nodes unicasts a reply message to the node which broadcasted the message to establish feedback routes which are reverse of the transfer routes.
The above-mentioned AOMDV has the following characteristics. Although a message received later is normally abandoned unconditionally if a broadcasted message is received in duplicate, in the AOMDV method, the receiving node (I) refers to the above-mentioned address registration area in the message, and if the address is different from the message (N1) which is already received, a process for renewing the feedback routes is performed, i.e., the node (I) unicasts a RREP to the source node of transmitting the message. In this manner, the node I establishes distinct links N1 and N2 and becomes a relay node at which the two links cross over. As a result, a plurality of routes having no overlapped links are established.
However, in the above-mentioned method, there are the following problems. That is, as shown in FIG. 12, if a plurality of relay nodes X and Y which correspond to the node I and at which plural links cross over, are present, an overlapped link connecting X-N3-Y is generated between the relay nodes X and Y. The reason for the formation of this overlapped link is as follows. The node X, when it receives a RREQ message from the nodes N1 and N2, broadcasts only the message (N1) which is received first. Although the message is broadcasted to the node Y via the nodes N3 and N4, the node Y unconditionally abandons the message which is received later since the addresses thereof are the same (N1). As a result, the route which passes through the node N4 is not established, and the above-mentioned overlapped link is generated.